#include "GTaskQueue.h"

#include "GError.h"
#include "GTimer.h"
#include "GTaskManager.h"
#include "GScopedLock.h"

namespace GEngine
{

	bool GTaskQueue::IsFull() const
	{
		return Queue.size() == G_TASK_QUEUE_MAX_SIZE;
	}

	bool GTaskQueue::IsEmpty() const
	{
		return Queue.size() == 0;
	}

	GSize GTaskQueue::GetCount() const
	{
		return Queue.size();
	}

	bool GTaskQueue::Supply(GTaskQueue* OtherQueue)
	{
		//GUtil::GError::DebugCheck(!NotEmpty.IsCreated(), "Scheduler not created.");

		// Scoped locks for easy free
		GThread::GScopedLock<GThread::GSpinMutex> MyLock(Lock);
		GThread::GScopedLock<GThread::GSpinMutex> OtherLock(OtherQueue->Lock);

		// If cannot lock do not wait
		if (!MyLock.TryAcquire())
		{
			return false;
		}

		if (IsEmpty())
		{
			// Leave if cannot supply
			return false;
		}

		// Try to lock the other queue
		if (!OtherLock.TryAcquire())
		{
			// Probably a task has arrived
			// Abort stealing
			return true;
		}

		if (!OtherQueue->IsEmpty())
		{
			// Other queue have tasks
			return true;
		}

		// At this point we are sure that we will supply something
		// If we have only one task share it
		if (GetCount() == 1)
		{
			// We have both locks
			// So just add to other queue
			GTask* NewTask = NULL;
			GTask* LastTask = Queue.front();

			// Is it stealable
			if (!LastTask->CheckThreadSafe())
			{
				return false;
			}

			// Divide our last task
			bool Divided = LastTask->Divide(&NewTask);
			if (!Divided)
			{
				return false;
			}

			// We have both queue locks
			// Supply into other queue directly
			OtherQueue->Queue.push_back(NewTask);
			return true;
		}

		// How many we can supply
		GSize SupplyCount = GetCount() / 2;
		if (SupplyCount > G_TASK_YIELD_MAX_SIZE)
		{
			SupplyCount = G_TASK_YIELD_MAX_SIZE;
		}

		// Steal tasks from the begining of the queue
		TaskListType::iterator End = Queue.end();
		TaskListType::iterator Iter = Queue.begin();
		TaskListType::iterator Next = Queue.begin();

		GSize FoundCount = 0;
		while ((FoundCount < SupplyCount) && (Iter != End))
		{
			// Check if the task is stealable
			if (!(*Iter)->CheckThreadSafe())
			{
				Iter++;
				continue;
			}

			// Keep next position
			Next = Iter;
			Next++;

			// We have both queue locks
			// Transfer task to requesting queue's list
			// Iter shows the same item but in other Queue
			OtherQueue->Queue.splice(OtherQueue->Queue.end(), Queue, Iter);

			FoundCount++;

			// Restore iterator to this queue's next item
			Iter = Next;
		}

		return true;
	}
	
	GTaskQueue::GTaskQueue()
	{
	}

	GTaskQueue::~GTaskQueue()
	{
	}

	void GTaskQueue::Clear()
	{
		Lock.Acquire();
		Queue.clear();
		Lock.Free();
	}

	bool GTaskQueue::Steal()
	{
		GUtil::GError::DebugCheck(Victims.size() == 0, "There are no victims to steal from.");
		
		// There will be core count schedulers
		GSize VictimCount = Victims.size();

		// Start with a random index and run Count iterations
		GSize Offset = (GSize)GUtil::GTicks::QueryTickCount() % VictimCount;

		for (GSize I = 0; I < VictimCount; ++I)
		{
			GSize TargetIndex = (Offset + I) % VictimCount;

			// Dont steal from myself
			if (Victims[I] == this)
			{
				continue;
			}

			// Request tasks from target queue
			if (Victims[I]->Supply(this))
			{
				return true;
			}
		}

		return false;
	}

	bool GTaskQueue::Pop(OUTPUT GTask** OutTask)
	{
		//GUtil::GError::DebugCheck(!NotEmpty.IsCreated(), "Scheduler not created.");

		// Scoped locks for easy free
		GThread::GScopedLock<GThread::GSpinMutex> MyLock(Lock);

		// Enter critical section
		MyLock.Acquire();

		if (Queue.size() == 0)
		{
			return false;
		}

		GTask* Task = Queue.back();

		// Check if we can reduce
		bool Reduced = Task->Reduce(OutTask);
		if (Reduced)
		{
			return true;
		}
		
		// Otherwise give the whole task
		*OutTask = Task;
		Queue.pop_back();

		return true;
	}

	bool GTaskQueue::Push(GTask* Task)
	{
		//GUtil::GError::DebugCheck(!NotEmpty.IsCreated(), "Scheduler not created.");
		
		// Scoped locks for easy free
		GThread::GScopedLock<GThread::GSpinMutex> MyLock(Lock);

		// Enter critical section
		MyLock.Acquire();
		
		// Check queue size
		if (Queue.size() > G_TASK_QUEUE_MAX_SIZE)
		{
			return false;
		}

		Queue.push_back(Task);

		return true;
	}

	bool GTaskQueue::Create(GTaskQueue** VictimArr, GSize VictimCount)
	{
		// be sure this queue is not a victim
		Victims.reserve(VictimCount);
		for (GSize I = 0; I < VictimCount; ++I)
		{
			if (VictimArr[I] != this)
			{
				Victims.push_back(VictimArr[I]);
			}
		}
	
		return true;
	}
	
	void GTaskQueue::Release()
	{
		Victims.clear();
	}

}